package com.mdnote.structure.treebaswe;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/29 
 * @description 二叉树查找
 */
public class BinaryTreeSearch {

    /**
     * 节点
     */
    private static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        /**
         * 谦虚查找
         */
        private Node preFind(int value) {
            if (this.value == value) {
                return this;
            }
            Node temp = null;
            if (this.left != null) {
                temp = this.left.preFind(value);
            }
            if (temp != null) {
                return temp;
            }
            if (this.right != null) {
                temp = this.right.preFind(value);
            }
            return temp;
        }

        /**
         * 终须查找
         */
        private Node infixFind (int value) {

            Node temp = null;
            if (this.left != null) {
                temp = this.left.infixFind(value);
            }
            if (temp != null) {
                return temp;
            }
            if (this.value == value) {
                return this;
            }
            if (this.right != null) {
                temp = this.right.infixFind(value);
            }
            return temp;
        }

        /**
         * 后续查找
         */
        private Node postFind(int value) {
            Node temp = null;
            if (this.left != null) {
                temp = this.left.infixFind(value);
            }
            if (temp != null) {
                return temp;
            }
            if (this.right != null) {
                temp = this.right.infixFind(value);
            }
            if (temp != null) {
                return temp;
            }
            if (this.value == value) {
                return this;
            }
            return temp;
        }
    }

    private Node root;

    public BinaryTreeSearch(Node root) {
        this.root = root;
    }

    private Node preFind(int value) {
        Node node = root.preFind(value);
        if (node == null) {
            throw new RuntimeException("没有找到钙元素");
        }
        return node;
    }

    private Node infixFind(int value) {
        Node node = root.infixFind(value);
        if (node == null) {
            throw new RuntimeException("没有找到钙元素");
        }
        return node;
    }

    private Node postFind(int value) {
        Node node = root.postFind(value);
        if (node == null) {
            throw new RuntimeException("没有找到钙元素");
        }
        return node;
    }

    public static void main(String[] args) {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        Node node4 = new Node(44);
        Node node5 = new Node(55);


        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);

        BinaryTreeSearch binaryTreeSearch = new BinaryTreeSearch(node1);

        System.out.println("前序查找");
        // 应该是 11 22 44 55 33
        System.out.println(binaryTreeSearch.preFind(44));
        System.out.println();
        System.out.println("中序查找");
        // 应该是 44 22 55 11 33
        System.out.println(binaryTreeSearch.infixFind(44));
        System.out.println();
        System.out.println("后序查找");
        // 应该是 44 55 22 33 11
        System.out.println(binaryTreeSearch.postFind(44));
    }
}
